package utility.pathfinding;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;

import model.Element;
import model.World;
import model.element.Road;

public class Pathfinding {
	private static final int MAXIMUM_ITERATIONS = 10000;
	
	public static LinkedList<Road> anotherDFS(Road start, Road end){
		HashSet<Road> finishedNodes = new HashSet<Road>();
		LinkedList<Road> currentPath = new LinkedList<Road>();
		currentPath.addLast(start);
		
		return anotherDFSIn(end, currentPath, finishedNodes);
	}
	
	private static LinkedList<Road> anotherDFSIn(Road end, LinkedList<Road> currentPath, HashSet<Road> finishedNodes){
		
		if(currentPath.isEmpty()){
			System.out.println("Could not find a solution.");
			return null;
		}
		else if(currentPath.peekLast() == end){
			System.out.println("Found a solution!");
			return currentPath;
		} else {
			System.out.println("Peek: "+currentPath.peekLast().getRectangle());
			Road r = closestToDestination(currentPath.peekLast(), end, currentPath, finishedNodes);
			if(r == null){
				Road temp = currentPath.removeLast();
				finishedNodes.add(temp);
				return anotherDFSIn(end, currentPath, finishedNodes);
			} else {
				System.out.println(r.getRectangle());
				currentPath.addLast(r);
				return anotherDFSIn(end, currentPath, finishedNodes);
			}
		}
	}
	
	/* "Fredriko Prantaro DFS" aka "stupido visitoro search algorithm" - perfect for simulating real human pathfinding */
	public static LinkedList<Road> depthFirst(Road start, Road end, World w){
		int i = 0;
		
		HashSet<Road> finishedNodes = new HashSet<Road>();
		LinkedList<Road> currentPath = new LinkedList<Road>();
		
		currentPath.addFirst(start);

		/* while we have not reached goal or limit */
		while(i < MAXIMUM_ITERATIONS && currentPath.peekFirst() != end && !currentPath.isEmpty()){
			Road r = closestToDestination(currentPath.peekFirst(), end, currentPath, finishedNodes);
			if(r == null){
				/* couldn't find a nearby node that was unvisited */
				Road temp = currentPath.removeFirst();
				System.out.println("RM: "+temp.getRectangle());
				finishedNodes.add(temp);
			} else {
				/* found a nearby node */
				currentPath.addFirst(r);
				if(r == end){
					return currentPath;
				}
			}
			i++;
		}	
		return currentPath;
	}
	
	private static Road closestToDestination(Road start, Road end, LinkedList<Road> currentPath, HashSet<Road> finishedNodes){
		/* for now just pick a random non-visited node */
		ArrayList <Road> tempArray = start.getNearbyRoads();
		
		for(Road r : start.getNearbyRoads()){
			if(!(currentPath.contains(r)) && !(finishedNodes.contains(r))){
				return r;
			}
		}

		return null; 
	}
	
	
}
